package com.suo.ADT;

import java.nio.BufferUnderflowException;

public class BinarySearchTree {
    private static class BinaryNode {
        BinaryNode(Integer theElement) {
            this(theElement,null,null);
        }

        public BinaryNode(Integer element, BinaryNode left, BinaryNode right) {
            this.element = element;
            this.left = left;
            this.right = right;
        }

        //节点中的数据
        Integer element;
        //左孩子
        BinaryNode left;
        //右孩子
        BinaryNode right;
    }

    //根节点
    private BinaryNode root;

    //无参构造
    public BinarySearchTree() {
        root = null;
    }

    //清空树
    public void makeEmpty() {
        root = null;
    }

    //判断树是否为空
    public boolean isEmpty() {
        return root == null;
    }

    //判断树是否含有某个节点
    public boolean contains(Integer x) {
        return contains(x,root);
    }

    //寻找这颗树的最小值
    public Integer findMin() {
        if (isEmpty()) throw  new BufferUnderflowException();
        return findMin(root).element;
    }

    //寻找这颗树的最大值
    public Integer findMax() {
        if (isEmpty()) throw  new BufferUnderflowException();
        return findMax(root).element;
    }

    //插入操作
    public void insert(Integer x) {
        root = insert(x,root);
    }

    //删除操作
    public void remove(Integer x) {
        root = remove(x,root);
    }

    //遍历操作
    public void printTree() {
        printTree(root);
        System.out.println();
    }


    /**
     * 如果相等则返回本节点，如歌比根节点小则递归左子树，如果比根节点大则递归右子树
     * @param x
     * @param t
     * @return
     */
    private boolean contains(Integer x,BinaryNode t) {
        if(t == null) return false;
        if(x == t.element) return true;
        else if(x < t.element) return contains(x,root.left);
        else return contains(x,root.right);
    }

    /**
     * 一直往左走
     * @param t
     * @return
     */
    private BinaryNode findMin(BinaryNode t) {
        if (t == null) return null;
        while(t.left != null) {
            t = t.left;
        }
        return t;
    }

    /**
     * 一直往右走
     * @param t
     * @return
     */
    private BinaryNode findMax(BinaryNode t) {
        if (t == null) return null;
        while(t.right != null) {
            t = t.right;
        }
        return t;
    }

    /**
     * 如果比根节点小往左插，反之往右插，不考虑相等的情况
     * @param x
     * @param t
     * @return
     */
    private BinaryNode insert(Integer x, BinaryNode t) {
        if (t == null) {
            return new BinaryNode(x,null,null);
        }

        if (x < t.element) {
            t.left = insert(x, t.left);
        }
        else if(x > t.element) {
            t.right = insert(x, t.right);
        }
        else {
            //do nothing
        }
        return t;
    }

    /**
     * 如果要删除的节点是叶子节点，没有孩子那么直接删除
     * 如果要删除的节点又一个孩子，则直接用孩子节点来替换
     * 如果要删除的节点有两个孩子，用右子树的最小值或左子树的最大值；爱替换然后删除用于替换的那个节点
     * @param x
     * @param t
     * @return
     */
    private BinaryNode remove(Integer x,BinaryNode t) {
        if (t == null) {
            return t;
        }

        if (x < t.element) {
            t.left = remove(x,t.left);
        }
        else if (x > t.element) {
            t.right = remove(x,t.right);
        }
        else {
            if (t.left == null && t.right == null) {
                t = null;
            }
            else if(t.left == null || t.right == null) {
                t = (t.left == null) ? t.right : t.left;
            }
            else {
                t.element = findMin(t.right).element;
                t.right = remove(t.element,t.right);
            }
        }
        return t;
    }

    private void printTree(BinaryNode t) {
        if (t == null) {
            return;
        }
        printTree(t.left);
        System.out.print(t.element + " ");
        printTree(t.right);
    }
}
